#include "string_array.h"

using namespace std;

//初始化
myStr::myStr(const char* str){
    length=0;
    while(str[length]!='\0'){
        length++;
    }
    data=new char[length+1];
    for(int i=0;i<length;i++){
        data[i]=str[i];
    }
    data[length]='\0';
    next=new int[length];
    nextVal=new int[length];
    for(int i=0;i<length;i++){
        next[i]=0;
        nextVal[i]=0;
    }
}

//销毁
myStr::~myStr(){
    delete[] data;
    delete[] next;
    delete[] nextVal;
    //length=0;          //?
}

//串的替换
bool replaceStr(myStr& S, const int& start, const myStr& t, const myStr& v){
    if(start<1||start>S.length){
        return false;
    }
    bool found=false;
    int index=-1;
    for(int i=start-1;i<=S.length-t.length;i++){
            bool match=true;
            for(int j=0;j<t.length;j++){
                if(S.data[j+i]!=t.data[j]){
                    match=false;
                    break;
                }
            }
            if(match){
                found=true;
                index=i;
                break;
            }
    }
    if(!found){
        return false;
    }
    int newlength=S.length-t.length+v.length;
    char* newS=new char[newlength+1];
    for(int i=0;i<index;i++){
        newS[i]=S.data[i];
    }
    for(int i=0;i<v.length;i++){
        newS[i+index]=v.data[i];
    }
    for(int i=index+t.length;i<S.length;i++){
        newS[i-t.length+v.length]=S.data[i];
    }
    newS[newlength]='\0';

    delete[] S.data;
    S.data=newS;
    S.length=newlength;

//规范；初始化
    delete[] S.next;
    delete[] S.nextVal;
    S.next = new int[newlength];
    S.nextVal = new int[newlength];
    for (int i = 0; i < newlength; i++) {
        S.next[i] = 0;
        S.nextVal[i] = 0;
    }
    
    return true;
}
/*
//kmp辅助数组next的计算
void myStr::kmp_next(){
    next=new int[length];
    next[0]=0;
    next[1]=1;
    for(int i=2;i<=length;i++){
        int j=next[i-1];
        bool flag=true;
        while(j){
            for(int r=0;r<j;r++){
                if(data[r]!=data[i-j+r]){
                    flag=false;
                    break;
                }
            }
            if(flag) break;
            else j--;
        }
        next[i]=j+1;
    }
}
*/

void myStr::kmp_next() {
    next=new int[length];  
    if(length==0) return; 
    next[0]=0;
    if(length>=1) next[1]=1;
    for (int i = 2; i <= length; ++i) {
        int j = next[i-1]; 
        while (j > 0 && data[j-1] != data[i-1]) {
            j=next[j]-1; 
        }
        if(j>0){
            ++j;
        }
        next[i]=(j==0) ? 1 : j;
    }
}

void myStr::kmp_nextVal() {
    if(length<=0) return;
    kmp_next();
    nextVal[0]=0; 
    for (int i=1;i<length;i++) {
        if (data[i]==data[next[i]-1]) {
            nextVal[i]=nextVal[next[i]-1];
        } else {
            nextVal[i]=next[i];
        }
    }
}

int simpleMatch(const myStr& S,const myStr& T){
    if(T.length>S.length){
        return -1;
    }
    for(int i=0;i<=S.length-T.length;i++){
        bool flag=true;
        for(int j=0;j<T.length;j++){
            if(S.data[i+j]!=T.data[j]){
                flag=false;
                break;
            }
        }
        if(flag){
            return i+1;
        }
    }
    return -1;
}

int kmpMatch(const myStr& S, const myStr& T){
    if(T.length>S.length){
        return -1;
    }
    if(T.length==0){
        return -1;
    }
    myStr T_copy(T.data);
    T_copy.kmp_next();
    int i=0;
    int j=0;
    while(i<S.length&&j<T.length){
        if(j==-1||S.data[i]==T.data[j]){
            i++;
            j++;
        }
        else{
            j=T_copy.next[j]-1;
        }
    }
    if(j==T.length){
        return i-T.length+1;
    }
    else{
        return -1;
    }

}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}
//初始化
myMatrix::myMatrix(const int& rnum, const int& cnum, const int& nnum, const int* data){
    rowNum=rnum;
    colNum=cnum;
    nodeNum=nnum;
    nodeList=new matrixNode[nodeNum];
    for(int i=0;i<nodeNum;i++){
        nodeList[i].row=data[i*3];
        nodeList[i].col=data[i*3+1];
        nodeList[i].value=data[i*3+2];
    }
}

//无参数构造函数
myMatrix::myMatrix(){
    rowNum=0;
    colNum=0;
    nodeNum=0;
    nodeList=nullptr;
}

//销毁稀疏矩阵
myMatrix::~myMatrix(){
    delete[] nodeList;
}

//快速转置
void myMatrix::FastTransposeSMatrix(myMatrix& T){
    T.rowNum=colNum;
    T.colNum=rowNum;
    T.nodeNum=nodeNum;
    T.nodeList=new matrixNode[nodeNum];
    if(nodeNum==0){
        return;
    }
    int* num=new int[colNum+1];
    int* cpot=new int[colNum+1];
    if(T.nodeNum){
        for(int i=1;i<=colNum;i++){
            num[i]=0;
        }
        for(int i=0;i<nodeNum;i++){
            ++num[nodeList[i].col];
        }
        cpot[1]=0;
        for(int i=2;i<=colNum;i++){
            cpot[i]=cpot[i-1]+num[i-1];
        }
        for(int i=0;i<nodeNum;i++){
            int col=nodeList[i].col;
            int pos=cpot[col];
            T.nodeList[pos].row=nodeList[i].col;
            T.nodeList[pos].col=nodeList[i].row;
            T.nodeList[pos].value=nodeList[i].value;
            cpot[col]++;
        }
         delete[] num;
         delete[] cpot;
    }
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
